package chapter03;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * 给定两个已排序的表L1、L2，只使用基本的表操作编写计算L1、L2的交集
 */
public class Q4<E> {

    /**
     * 时间复杂度
     * @param L1
     * @param L2
     * @param interSect
     * @param <E>
     */
    public static <E extends Comparable<? super E>> void intersection(List<E> L1, List<E> L2, List<E> interSect) {
        Iterator<E> iterL1 = L1.iterator();
        Iterator<E> iterL2 = L2.iterator();
        E itemL1 = null, itemL2 = null;
        if (iterL1.hasNext() && iterL2.hasNext()) {
            itemL1 = iterL1.next();
            itemL2 = iterL2.next();
        }
        while (itemL1 != null && itemL2 != null) {
            int compareResult = itemL1.compareTo(itemL2);
            if (compareResult < 0) {
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
            } else if (compareResult > 0) {
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            } else {
                interSect.add(itemL1);
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            }
        }
    }


    public static <E extends Comparable<? super E>> void union(List<E> L1, List<E> L2, List<E> result) {
        Iterator<E> iterL1 = L1.iterator();
        Iterator<E> iterL2 = L2.iterator();
        E itemL1 = null, itemL2 = null;
        if (iterL1.hasNext() && iterL2.hasNext()) {
            itemL1 = iterL1.next();
            itemL2 = iterL2.next();
        }
        while (itemL1 != null && itemL2 != null) {
            int compareResult = itemL1.compareTo(itemL2);
            if (compareResult < 0) {
                result.add(itemL1);
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
            } else if (compareResult > 0) {
                result.add(itemL2);
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            } else {
                result.add(itemL1);
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            }
        }
        while (itemL1 != null) {
            result.add(itemL1);
            itemL1 = iterL1.hasNext() ? iterL1.next() : null;
        }
        while (itemL2 != null) {
            result.add(itemL2);
            itemL2 = iterL2.hasNext() ? iterL2.next() : null;
        }
    }

    public static void main(String[] args) {
        List<Integer> L1 = new ArrayList<Integer>();
        L1.add(1);
        L1.add(2);
        L1.add(3);

        List<Integer> L2 = new ArrayList<Integer>();
        L2.add(2);
        L2.add(4);
        List<Integer> interSection = new ArrayList<>();
        intersection(L1, L2, interSection);
        System.out.println(interSection);

        List<Integer> unionSection = new ArrayList<>();
        union(L1, L2, unionSection);
        System.out.println(unionSection);


    }
}
